• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Discovery procedure of multiple disjoint paths in a network node and step. The present invention describes a distributed procedure that allows discovering multiple disjoint paths between nodes in a network. The proposal proposes a mechanism that searches for multiple disjoint paths, either in links or in nodes, using network exploration techniques. The novelty is that, with a single network exploration process, multiple disjoint paths are discovered between a source node and all the other nodes in the network. Thanks to the use of exploration techniques, the procedure does not require prior topological knowledge of the network, so it does not need to rely on additional mechanisms that provide such topological information. This proposal constitutes a significant advantage over solutions that need to repeat the discovery or computation process as many times as disjoint paths are to be obtained, and this in turn repeated for each possible destination within the network. (Machine-translation by Google Translate, not legally binding)
    公开号:ES2827842A1
    申请号:ES201931036
    申请日:2019-11-22
    公开日:2021-05-24
    发明作者:Sánchez Elisa Rojas；Pajares Diego López；Pelayo Juan Antonio Carral；Horcajo Joaquín Alvarez
    申请人:Universidad de Alcala de Henares UAH；
    IPC主号:
    专利说明:

    [0004] TECHNICAL SECTOR
    [0005] The present invention falls within the field of communications and electronic devices and / or computer algorithms that operate in a distributed network.
    [0007] BACKGROUND OF THE INVENTION
    [0008] A network graph is a graphical representation of nodes and links connected through gates. The nodes represent the element / device with information processing capacity (they are capable of generating, processing, sending and receiving messages to / from their neighboring nodes), while the links represent the communication paths between nodes. In addition, the union between both elements is made through connecting doors. Links are considered to be always bidirectional (they allow communication in both directions). Likewise, each link is associated with a metric that determines the cost incurred when an information message is sent through it. We will say that two nodes are neighbors when there is a link that communicates them directly. The graph (network) can be known by the network administrator, or in the case of being unknown, it can be discovered through the use of topological discovery protocols such as LLDP ( Link Layer Discovery Protocol) [1]. The succession of nodes and links between nodes that make it possible to get an information message from any node of the network, hereinafter source node, to any other node of the network, hereinafter destination node, constitutes a path between these two nodes. We will say that two paths (between the same pair of source and destination nodes) are disjoint in links when they do not have any link in common. In the same way, we will say that two paths (between the same pair of source and destination nodes) are disjoint at nodes when there is no node common to both paths (except for the source and destination nodes themselves). Two paths disjoint at nodes are also, by definition, disjoint at links.
    [0010] Under these premises, the procedures that look for disjoint paths are known (in links and / or in nodes) based on computing techniques. These proposals calculate multiple disjoint paths between two nodes making use of algorithms that operate on the network graph, such as Suurballe [2], who presents a method to calculate two disjoint paths in a graph with a positive cost metric. Bhandari [3] modifies the Suurballe algorithm to adapt it to optical networks in order to achieve a second backup path. In [4] similar processes to those proposed by Bhandari are carried out including, in addition, optical restrictions of prohibited turns to avoid that the algorithm provides erroneous configurations in the optical nodes. In [5] a procedure is proposed to calculate two disjoint paths in links by means of a modification of the Dijkstra algorithm [6]. Said modification obtains a second disjoint path at the cost of not obtaining all the paths of least cost between the source and destination nodes. Likewise, [7] is also based on the Dijkstra algorithm to obtain disjoint paths from several source nodes to the same destination node. The procedure describes three well-defined phases. The first phase looks for two disjoint paths using Dijkstra's algorithm, or similar algorithms. The second phase interconnects the intermediate nodes that only have one route to reach their destination, with nodes that belong to the other branch of the path. In this way, all the nodes that belong to the two previously calculated paths now have two disjoint paths from them to the destination. The third phase looks for intermediate nodes that can reach the destination, and if they exist, it reapplies the first two phases.
    [0012] However, not all the proposals are based on applying a centralized computation algorithm on a known network graph, but there are also others that distribute that computation among the nodes that make up said network, each one handling local information (its information and that of your neighbors). The topological information required for the calculations can be distributed to all nodes in the network by broadcasting a specific topological message, or by exchanging messages between neighboring nodes containing the local topological information. Within the first approach, the Ibáñez [8] procedure fits, which is based on diffusion techniques, combined with recursive methods, to obtain multiple disjoint paths, either in links or in nodes, between a source node and a destination node. . The proposal consists of two phases, based on the procedures described in [9], [10] [11], [12], which are repeated iteratively. The first phase (network scan) discovers the topology by sending a message from the source node, and its subsequent dissemination throughout the network. The second phase (path confirmation) sends a confirmation message from the destination node to the source node, which is responsible for confirming the path with the previous information. In the following iterations, the paths discovered in previous iterations are discarded to ensure that the new paths are disjoint from the previous ones. Another procedure, such as the one described by Tanaka [13], also uses network exploration techniques, but starting from a previously given path. This path maintains active communication between a source node and a destination node. The procedure describes a network scanning mechanism based on message flooding and subsequent path confirmation to obtain a second path disjoint from the starting path.
    [0014] Within the second approach (exchange of messages between neighbors), Van der Kluit [14] proposes a method that discovers disjoint paths in links between a source node and a destination node. To do this, it is based on the exchange of messages between neighbors following the principles of the Bellman-Ford algorithm [15]. In addition, the proposal guarantees that the roads discovered are of minimum cost.
    [0016] The problem of finding multiple disjoint paths is also studied in wireless networks (whose links are via radio instead of wired). This is the case of [16] and [17], where disjoint paths are searched iteratively through the exchange of messages between neighbors. Likewise, there are proposals based on routing protocols for wireless networks such as Ad Hoc Distance Vector (AODV) [18] or Dynamic Source Routing (DSR) [19], such as [20], [21], [22] and [23 ]. These jobs calculate disjoint paths by exchanging messages between neighbors and subsequently comparing duplicate messages. With this exchange of messages and their comparison, the disjoint paths between the nodes of the network are updated and forwarded.
    [0018] Other works are also known that allow obtaining multiple paths between two nodes of the network, but that do not guarantee that these are disjoint (neither in nodes, nor in links). [24] provides multiple paths by applying a computational algorithm on a representation of the network map. Minkerberg [25] proposes a procedure to discover multiple paths with the number of hops metric, while in [26] a mechanism is established that modifies the original format of the Ethernet frame and exchanges the modified frames to obtain multiple roads. Other proposals that obtain multiple paths without guaranteeing whether or not they are disjoint are [27], [28], [29], [30] and [31].
    [0020] EXPLANATION OF THE INVENTION
    [0021] The present invention describes One Shot Multiple Disjoint Path (1S-MDP), a distributed procedure that allows the discovery of multiple disjoint paths between any node in the network and all the others. The specific application of the invention is for the calculation of paths between border nodes of a network. A border node is understood to be any node that has some end device connected, or that interconnects networks or subnets, or that is specifically selected by the network administrator.
    [0023] The proposal proposes a mechanism that searches for multiple disjoint paths, either in links or in nodes, using network exploration techniques. The novelty of this proposal lies in the fact that, with a single exploration process, in a network composed of N nodes, of which all, or a subset M, are boundary, the procedure allows discovering multiple disjoint paths between an origin boundary node, and the remaining M-1 border nodes taken as destination node. Thanks to the use of exploration techniques, the procedure does not require prior topological knowledge of the network, so it does not need to rely on additional mechanisms that provide such topological information.
    [0025] This procedure consists of two phases: an exploration phase, followed by another independent path selection phase for each disjoint path to be discovered. The exploration phase begins at the source node and is performed only once regardless of the number of nodes and paths to discover. This node creates a browse message that contains the identifier of the source node and a specific code that identifies it as a browse message. After the source node has created the message, it sends it to its neighbors through all of its gateways. All nodes in the network must be able to identify the browsing messages they receive from other nodes, by their message code, and process them. Upon receiving a scan message, the node in question associates the identifier of the source node of the scan message with the port through which said message arrived and stores said information; it then forwards the message to its neighboring nodes through all its doors. As a result of this process, repeated in all nodes on the network, a node can receive late copies of the original scan message (with a maximum of one copy for each gateway it has). In this case, the node receives, analyzes the message and saves the information collected in the same way, only that, when saving the information learned, the insert respects the metric of the procedure. For example, if the metric corresponds to a time dependency, the saved data will respect the order of arrival of the messages. Finally, being a late copy of the scan message, the node deletes the message instead of forwarding it to avoid message storms that can saturate the network.
    [0027] The path selection phase is initiated by any border node in the network that receives a scan message from a source node. From that moment on, the node in question becomes a target node. For each scan message received from a source node, the destination node creates a path selection message that includes the identifier of the source node, its identifier (destination node), a message code that identifies all selection messages, and a path identifier that is unique among the source-destination node pair. In addition, the message has a specific field to include the identifiers of the nodes and the entry and exit ports that the disjoint path that is being discovered traverses. The destination node includes its node identifier and the entry and exit ports that guarantee the disjoint path in the path selection message, and sends it to the source node through the same port through which the scan message was received. All the nodes of the network must be able to identify the path selection messages that they receive from other nodes, by their message code and process them. Upon receiving a path selection message, the node in question analyzes the message, obtaining from it the identifiers of the source and destination nodes, and the path identifier, and also notes the port through which said selection message arrived. With this information, the node selects a neighboring node from among those from which it received the corresponding exploration message so that it constitutes a disjoint path, either in links or in nodes (depending on the mode of operation) with respect to other discovered paths. above for the same source-destination node pair. If there are several possibilities, the one with the highest priority is selected following the order established by the metric in use. Finally, the node saves the information associated with the new disjoint path, includes it in the path selection message, and forwards said message through the appropriate port so that it reaches the origin. The selection phase The path ends when the source node receives the path selection message, or a node on the network does not find any disjoint paths. In the event that the node does not have a neighboring node that provides it with a disjoint path to those already known previously, it is possible to go back one step to the previous node so that it looks for a new disjoint path alternative. To do this, the node creates a special back-pass message, including the identifiers of the source and destination nodes, the path identifier, and the message code that identifies all back-pass messages. The step back message is sent to the previous node, which, following the process of the path selection phase, selects a new disjoint path. If the new node does not find a disjoint path, it can go back again. The back-step process ends when the back-step message reaches the node that started the path selection process, or when a predetermined maximum number of hops has been reached. The described proposal reduces the number of messages exchanged to discover the multiple disjoint paths thanks to the use of a single exploration process. Furthermore, the path selection phase runs in parallel both for multiple paths with the same destination node and for different destination nodes, thus reducing the total time consumed in the process (successive iteration is avoided).
    [0029] Functional modules of a 1S-MDP node
    [0030] Every 1S-MDP node is composed of a series of modules in charge of different functions: node initiation, message reception and creation of control messages, exploration, path selection and step back. In addition, each node has data structures to store the information collected in the different modules. The following sections detail each of the indicated modules.
    [0032] Node start
    [0033] After starting, a node that has 1S-MDP implemented waits a random time limited to a maximum value. During the random wait, the data structures that will store the information generated by the exploration, path selection and step back phases are started. The first data structure contains information about the scan of the network (scan table), while the second stores information about the disjoint paths that are discovered (selection table). These structures are local to each node and their management can be dealt with through temporary events, events associated with actions or in any other way.
    [0034] After the timeout, if the node in question is a boundary node, it initiates a disjoint path discovery process by generating a scan message and sending it through all its gates. This path discovery process can also be triggered by other internal or external events at any time.
    [0036] Message reception module
    [0037] The message reception module receives messages from neighboring nodes, and performs a first inspection of these to identify the type of message received and forward it to the corresponding processing module. If it is a message belonging to the 1S-MDP procedure, it analyzes the type of operation and forwards the message to the exploration module, path selection or step back as appropriate. If, on the other hand, the message does not belong to the 1S-MDP procedure, the message is forwarded through the standard procedure established for that purpose.
    [0039] Control message creation module
    [0040] Every 1S-MDP compliant node must have the ability to create control messages for scan, path selection, and step back. Once the message has been generated, the protocol identifier (1S-MDP), the type of operation (exploration, confirmation or step back), the mode of operation (disjoint in nodes or links) and the identifier of the source node are entered. in the fields designated for that purpose.
    [0042] If the type of operation is path selection or backward step, it also includes the identifier of the destination node and the identifier of the path (to distinguish it from other paths between the same pair of border nodes). Furthermore, these two operations require certain special actions. If the message to be created is a path selection message, it is checked whether the trigger is a previous step back message. If so, the field containing the information on the elements that make up the disjoint path (node identifiers and their entry and exit ports) is copied from the previous message and inserted into the new message. The discovered entry and exit gates that guarantee the new disjoint path are then added to this field, along with the node identifier. If, on the other hand, the path selection message is not preceded by a step back message, the new information is directly added (gates and route identifier). node). In the same way, for the creation of the backward step message, it is verified that the trigger is a previous path selection or step back message, and the field containing the elements that make up the disjoint path is copied. Next, the last element of the copied field is deleted (entry and exit doors together with their node identifier) since, when going back one step, that element will overwrite it in the next jump.
    [0044] If any field is not required, it is initialized to null, such as the fields that contain the destination node identifier and the path identifier in the scan message.
    [0046] Scan module
    [0047] The scanning module is in charge of processing the scanning messages that arrive from the message receiving module. When it receives a message, it analyzes the message field that contains the identifier of the source node, notes the port through which the message arrived, and creates a data pair with that information. Then, enter the pair in the drill table respecting the insertion order following the metric that has been established. For example, if a temporary metric is established, the entries will be entered according to the order of arrival, if the metric corresponds to the capacity of the link, the data will be entered according to the capacity of the link through which the message traveled, etc. . The stored information and its order of insertion in the table will be useful for the path selection module. Finally, the message received by all the doors of the node is forwarded only if it is the first scan message received from that source node, otherwise (late copies of the message), it is discarded. This selective forwarding prevents looping message storms that would overwhelm the network.
    [0049] If the node that receives the message is a border node, it must also start the path selection process in the direction back to the source node. To do this, a path selection control message is created in the message creation module, and it is sent to the border node, where the scan message originated, through the door through which said message was received.
    [0051] Path selection module
    [0052] The path selection module processes only path selection messages. path received from the message receiving module. The path selection module, when it receives a message, parses the message fields containing the identifiers of the source and destination nodes, the path identifier, and also notes the gateway of the path selection message. The first three identifiers uniquely describe the path, while the entrance door is used so that said door cannot be used by other paths, thus guaranteeing disjunctivity according to the indicated mode. The identifiers of the source and destination nodes are compared with the information contained in the path selection table. If there is no matching input, the message received corresponds to the first disjoint path for that pair of origin-destination nodes, so the output port with the highest available priority is selected. If there is a matching entry, the received message belongs to a path after the first disjoint path. In this case, the exit port with the highest priority is selected that guarantees disjunctivity with the previous paths, according to the mode of operation (disjoint in nodes or links). With all this information (identifiers of the source and destination nodes, path identifier and entry and exit ports) a tuple is created and inserted into the path selection table to guarantee the disjunctivity of subsequent paths. Next, the identifiers of the input and output ports of the message are inserted in the path selection message together with the identifier of the node in the field designated for this purpose. The objective is for the path selection message to record the information of the nodes that belong to the new disjoint path, in order to have a complete vision of the path when the path selection phase at the origin node ends. Finally, the path selection message to the source node is forwarded through the selected exit port.
    [0054] It is possible that a disjoint path will not be found when searching for the exit door. In this case, no insert is made in the path selection table, instead, a call is made to the message creation module to create a step back message based on the information contained in the path selection message. road. The created message is sent to the previous node through the input port of the selection message, with the aim that the previous node finds an alternative path to the one already explored, and that it ended up in a dead-end path, that fulfills the disjunctivity property required.
    [0056] The path selection phase ends when the selection message reaches the node source. The latter obtains from the message the information of the disjoint path discovered (which has been recorded step by step in the path selection process, and provides said information to the services that require it or stores it for future use.
    [0058] Step back module
    [0059] The back-pass module processes only the back-pass messages that it receives from the message-receiving module. It analyzes the identifiers of the source and destination nodes of the message, and verifies that the identifier of the source node of the message is different from the identifier of the node that received the message step backward. If it matches, the message has reached the node where it was created, and therefore no new output alternatives can be found. If it does not match, it searches for a new disjoint path for the source-destination node pair, updates the commit table, creates a new select message from which the failed step has been removed, and forwards the new message through the new selected exit port . In this new search, if the module does not find an alternative exit door that satisfies the disjunctivity property, it calls the message generation module to create a new back-pass message. In this way, as many steps as needed can be retraced until a viable path is found (the number of steps back could be limited by an additional configuration parameter).
    [0061] BRIEF DESCRIPTION OF THE DRAWINGS
    [0062] To complement the description that is being made and in order to help a better understanding of the characteristics of the invention, a set of drawings is attached as an integral part of said description, where, with an illustrative and non-limiting nature, where it has been represented the next:
    [0064] Figure 1.- Shows the exploration process of the invention from the origin node S. Figures 2, 4 and 6 occur at the same instant of time. The confirmations at the three border nodes run in parallel. To improve understanding, the process has been separated into three different figures.
    [0066] Figure 2.- Shows the confirmation process from node D1 with the nodes working in link mode.
    [0068] Figure 3.- Shows the disjoint paths in discovered links between node S and the node D1.
    [0070] Figure 4.- Shows the confirmation process from node D2 with the nodes working in link mode.
    [0072] Figure 5.- Shows the disjoint paths in discovered links between node S and node D2.
    [0074] Figure 6.- Shows the confirmation process from node D3 with the nodes working in link mode.
    [0076] Figure 7.- Shows the disjoint paths in discovered links between node S and node D3.
    [0078] Figures 8, 10 and 12 occur at the same instant in time. The confirmations at the three border nodes run in parallel. To improve understanding, the process has been separated into three different figures.
    [0080] Figure 8.- Shows the confirmation process from node D1 with the nodes working in node mode.
    [0082] Figure 9.- Shows the disjoint paths in discovered nodes between node S and node D1.
    [0084] Figure 10.- Shows the confirmation process from node D2 with the nodes working in node mode.
    [0086] Figure 11.- Shows the disjoint paths in discovered nodes between node S and node D2.
    [0088] Figure 12.- Shows the confirmation process from node D3 with the nodes working in node mode.
    [0090] Figure 13.- Shows the disjoint paths in discovered nodes between node S and node D3.
    [0091] Figure 14.- Shows the flow diagram of the node start.
    [0093] Figure 15.- Shows the flow chart to create a new message.
    [0095] Figure 16.- Shows the flow diagram of the reception of a message.
    [0097] Figure 17.- Shows the flow chart of the scanning module.
    [0099] Figure 18.- Shows the flow diagram of the path selection module.
    [0101] Figure 19.- Shows the flow diagram of the reverse step module.
    [0103] Figure 20.- Shows the message format and the exploration and confirmation tables.
    [0105] The flowcharts contain the following legends:
    [0106] ■ PROTO_ID: Protocol identifier
    [0107] ■ TIPO_OP: Type of operation (exploration, confirmation, step back)
    [0108] ■ OG_ID: Identifier of the source node
    [0109] ■ DT_ID: Identifier of the destination node
    [0110] ■ N_ID: Node identifier
    [0111] ■ C_ID: Path identifier
    [0112] ■ Q: Door on a device
    [0113] ■ PE: Gateway of the message in the device
    [0114] ■ PS: Exit port of the message on the device
    [0115] ■ CAM_DISJ: Set of nodes and gates that make up the disjoint path ■ TE: Exploration table
    [0116] ■ TS: Selection table
    [0117] ■ ENT_TS: Element of the selection table
    [0119] PREFERRED EMBODIMENT OF THE INVENTION
    [0120] A possible implementation of this example would be a communication network based on Ethernet technology. The nodes would be advanced network bridges that communicate using Ethernet technology. A specific EtherType will be used to distinguish the frames carrying 1S-MDP control messages from other frames on the network, and the MAC addresses of the bridges will be used as identifiers of the nodes. border (origin and destination).
    [0122] The Ethernet frames that carry 1S-MDP scan messages will have the source MAC address of the source border bridge as the source MAC address and the destination MAC address the address reserved for broadcasting (FF: FF: FF: FF: FF: FF) on Ethernet. If a scan message carries the address of a network border node as the destination address, only the multiple disjoint paths between the source node and that destination node will be discovered.
    [0124] The Ethernet frames that carry 1S-MDP path selection messages will have the source MAC address of the bridge that generated said message and the destination MAC address of the source border bridge (where it is intended to arrive). The Ethernet frames that carry 1S-MDP back-pass messages will have the source MAC address of the bridge that generated said message and the destination MAC address of the previous bridge on the path being retracted. The order of arrival of the scan frames to a bridge is used as a cost metric, therefore, between two path options, the one with the highest priority will always point to the fastest path available from the origin to that node among those discovered in the exploration phase.
    [0126] The paths discovered by the 1S-MDP procedure can be assigned to different traffic flows between network bridges to optimize load sharing (maximize overall network performance), improve reliability, increase security, or implement quality policies. service, among other options. With the objective of load sharing, flows can be distributed equitably among the different roads; to improve reliability, the most stable path or path with fewer hops can be used as the main path, leaving the others for backup functions, or critical traffic can also be forwarded on several paths at the same time; to improve security, the same flow can be divided between the different possible paths, for example, to avoid "man-in-the-middle"attacks; To provide different qualities of service, we can assign the fastest path to premium streams, and the remaining paths to streams with lower priority.
    [0128] Figures 1 to 7 show an example of the 1S-MDP path discovery process between the originating border bridge identified as node S and the border bridges. destination identified as nodes D1, D2 and D3 in disjoint mode in links.
    [0130] Figure 1 shows the exchange of frames with the scan messages. The first copy of the message received at each node is shown with a solid line and late copies of that message are shown with a double solid line. The order of arrival of the copies to a bridge is indicated by an increasing integer (1,2, ...).
    [0132] Figure 2 shows the exchange of the path selection messages originated in the destination border node D1 with the selections made in each intermediate node based on the gate order discovered in the previous scanning process. And figure 3 shows the paths discovered as a result of the process.
    [0134] Figures 4 and 5, and Figures 6 and 7, show the same path selection process for destination border nodes D2 and D3, respectively.
    [0136] In the same way, Figures 8 to 13 show an example of the 1S-MDP path selection process in node disjoint mode. It starts with the same exploration process presented in Figure 1.
    [0138] Figure 8 shows the exchange of the path selection messages originated in the destination border node D1 with the selections made in each intermediate node as a function of the gate order discovered in the previous scanning process. In this case, it can be seen how B must execute a back-step procedure in the process of selecting path number 3 since it has already been used for path number 2. Figure 9 shows the paths discovered as a result of the process.
    [0140] Figures 10 and 11, and Figures 11 and 12, show the same path selection process for destination border nodes D2 and D3, respectively.
    [0141] BIBLIOGRAPHY
    [0143] [1] IEEE Organization, "IEEE 802.1AB-2016 Station and Media Access Control Connectivity Discovery," IEEE Standard for Local and metropolitan area networks, 2016.
    [0144] [2] JW Suurballe, "Disjoint paths in a network," Networks, vol. 4, no. 2, pp. 125-145, 1974.
    [0145] [3] R. Bhandari, "Optimal diverse routing in telecommunication fiber networks," Proc. INFOCOM '94 Conf. Comput. Commun., No. 908, pp. 1498-1508, 1994.
    [0146] [4] K. Tomohiro Hashiguchi, K .; Toru Katagiri, K .; Kazuyuki Tajima, and K. Yutaka Takita, "Apparatus and method for finding a pair of disjoint paths in a communication network," US8345538B2, 2013.
    [0147] [5] C. (US); Jin Huai, Rohnert Park, CA (US); Gary Baldwin, Santa Rosa and C.
    [0148] (US) Anix Anbiah, Rohnert Park, "Method and apparatus for discovering edgedisjoint shortest path pairs during shortest path tree computation," US6928484B1, 2005.
    [0149] [6] EW Dijkstra, "A Note on Two Problems in Connexion with Graphs,” Numer.
    [0150] Math. , vol. 1, no. 1, pp. 269-271, 1959.
    [0151] [7] G. Schollmeier and C. Winkler, "Method and network node for determining multipath transmission paths in a packet-switched communication network," DE20031008615, 2005.
    [0152] [8] D. Ibañez Fernández, Guillermo; Álvarez Horcajo, Joaquín; Carral Pelayo, Juan Antonio; Martínez Yelmo, Isaías and López Pajares, "Procedure for the establishment and deletion of multiple disjoint paths, frame forwarding and network bridge," ES2638292B2, 2016.
    [0153] [9] G. Ibanez, JA Carral, A. Garcia-Martinez, JM Arco, D. Rivera, and A. Azcorra, "Fast Path Ethernet Switching: On-demand, efficient transparent bridges for data center and campus networks," in 2010 17th IEEE Workshop on Local & Metropolitan Area Networks ( LANMAN), 2010, pp. 1-7.
    [0154] [10] G. Ibanez, JA Carral, JM Arco, D. Rivera, and A. Montalvo, "ARP-Path: ARP-Based, Shortest Path Bridges," IEEE Commun. Lett., Vol. 15, no. 7, pp. 770 772, Jul. 2011.
    [0155] [11] E. Rojas Sánchez, G. Ibanez Fernández, I. Martínez Yelmo, and A. Azcorra Salona, "Procedure for establishing and erasing roads and forwarding frames for transport connections and network bridge,"ES2540595B2; PCT / ES2014 / 070905, 2016.
    [0156] [12] J. Alvarez-Horcajo, D. Lopez-Pajares, JM Arco, JA Carral, and I. Martinez-Yelmo, "TCP-path: Improving load balance by network exploration,” in 2017 IEEE 6th International Conference on Cloud Networking ( CloudNet), 2017, pp.
    [0157] 1-6.
    [0158] [13] K. Jun Tanaka, "Path Generating method, relay device, and Computer product," US008665754B2, 2014.
    [0159] [14] B. J. van der Kluit, A. C. G. Holtzer, B. M. M. Gijsen, and Hendrik Bernard Meeuwissen, "Search for disjoint paths thorugh a network,” 2017.
    [0160] [15] TH Cormen, CE Leiserson, RL Rivest, and C. Stein, Introduction to algorithms, Second. MIT Press, 2001.
    [0161] [16] K. Zhang, Q. Han, G. Yin, and H. Pan, "OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks," J. Comb. Optim., Vol. 31 , no. 4, pp. 1623-1641, 2016.
    [0162] [17] K. Zhang, G. Yin, Q. Han, and J. Lin, "DFDP: A Distributed Algorithm for Finding Disjoint Paths in Wireless Sensor Networks with Correctness Guarantee," Int. J. Distrib. Sens. Networks, vol . 10, no. 6, p. 258959, Jun. 2014.
    [0163] [18] CE Perkins and EM Royer, "Ad-hoc on-demand distance vector routing," in Proceedings WMCSA'99. Second IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90-100.
    [0164] [19] D. B. Johnson, D. B. Johnson, D. A. Maltz, and J. Broch, "Dsr: The dynamic source routing protocol for multi-hop wireless ad hoc networks,” Ad hoc networking, ”pp. 139--172, 2001.
    [0165] [20] S.-J. Lee and M. Gerla, "Split multipath routing with maximally disjoint paths in ad hoc networks," in ICC 2001. IEEE International Conference on Communications. Conference Record ( Cat. No. 01CH37240), vol. 10, pp. 3201-3205.
    [0166] [21] Z. Ye, SV Krishnamurthy, and SK Tripathi, "A framework for reliable routing in mobile ad hoc networks," in IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies ( IEEE Cat. No 03CH37428), vol. 1, pp. 270-280.
    [0167] [22] MK Marina and SR Das, "On-demand multipath distance vector routing in ad hoc networks," in Proceedings Ninth International Conference on Network Protocols. ICNP 2001, pp. 14-23.
    [0168] [23] V. Loscri and S. Marano, "A new Geographic Multipath Protocol for Ad hoc Networks to reduce the Route Coupling phenomenon, ”in 2006 IEEE 63rd Vehicular Technology Conference, vol. 3, pp. 1102-1106.
    [0169] [24] G. W. Atkinson, "Mutually compatible path search," US10069717B2, 2018.
    [0170] [25] C. Minkenberg and M. R. Gusat, "Multipath discovery in switched ethernet networks." Google Patents, 31-Jan-2012.
    [0171] [26] J. Marukawa, Y. Nomura, S. Yamada, M. Terasawa, S. Okamoto, and N.
    [0172] Yamanaka, "Scalable multi-path discovery technique for parallel data transmission in next generation wide area layer-2 network," in 2011 1st International Symposium on Access Spaces ( ISAS), 2011, pp. 208-212.
    [0173] [27] A. Atlas, "Forwarding mechanisms for fast reroute using maximally redundant trees," 2015.
    [0174] [28] D. Fedyk and D. Allan, "IS-IS Extensions Supporting IEEE 802.1aq Shortest Path Bridging (SPB). RFC 6329," pp. 1-37, 2012.
    [0175] [29] H. Geng, X. Shi, Z. Wang, and X. Yin, "A hop-by-hop dynamic distributed multipath routing mechanism for link state network,” Comput. Commun., Vol.
    [0176] 116, pp. 225-239, Jan. 2018.
    [0177] [30] P. Hofmann, "Method and apparatus for discovering disjoint routes to multiple service nodes," EP1773003A1, 2005.
    [0178] [31] D. Lopez-Pajares, J. Alvarez-Horcajo, E. Rojas, A. S. M. Asadujjaman, and I.
    [0179] Martinez-Yelmo, "Amaru: Plug & Play Resilient In-Band Control for SDN," IEEE Access, vol. 7, pp. 123202-123218, 2019.
    [0181] THANKS
    [0182] The invention is partially the result of research carried out in the following projects:
    [0184] • "Integrated Technologies for Management and Operation of 5G network", Community of Madrid, TIGRE5-CM (S2013 / ICE-2919)
    [0185] • "Advanced Techniques to Enhance the Intelligence of 5G Networks", Community of Madrid, TAPIR-CM (S2018 / TCS-4496)
    权利要求:
    Claims (5)
    [1]
    1. Procedure for searching multiple disjoint paths in a single step, comprising the following stages:
    a) Carry out a network exploration process by means of the controlled diffusion of exploratory messages, from a source border node, to all other destination border nodes that make up the network.
    b) Selecting multiple disjoint paths from destination border nodes of scan messages generated by step a), sending a path selection message to the source node for each of the gates through which it has received a copy of said scan message.
    c) The ability to go back to the previous node, in the path selection process or in the step back process, in the event that a network node does not find an exit that guarantees the established disjunctivity conditions.
    d) Upon receipt at a node, an exploratory message with an origin and a 1S-MDP procedure label;
    1. Associate, in a data structure, for the purposes of scanning the network, the information from the source node to the reception port, together with an expiration indicator; 2. Order the association following the established metric; 3. Process the received exploratory message as follows:
    to. In case of being the first message, the processing will be to forward the message through all the active ports towards their neighboring nodes;
    b. In case of being the second message received or later, the processing will be discarded while the entry is not obsolete;
    e) When a path selection message is received at a node with a source node identifier, a destination node identifier, a 1S-MDP procedure label, a path identifier and the elements associated with said path;
    1. Associate, in a data structure, for the purpose of searching the disjoint path (in links or nodes) the information of the source and destination nodes, the path identifier, and the gateway of the path selection message; 2. Search for an exit door that guarantees that the sought path fulfills the condition of disjunctivity (in nodes or in links) with previous paths for the same pair of origin-destination nodes;
    3. Complete the data structure processed according to point e) 1
    4. Process the path selection message as follows:
    a) If the node has found an exit port that guarantees the disjunctivity conditions according to the mode of operation, the information regarding this new node is included in the message, and it is forwarded through the exit port;
    b) If the node has not found an exit port that guarantees the disjunctivity conditions according to the mode of operation, a step back message is generated and sent to the previous node through the entry port of the selection message;
    f) When a back-pass message is received at a node with a source node identifier, a destination node identifier, a path identifier, a 1S-MDP procedure label and the elements associated with said path;
    1. Associate, in a data structure, for the purpose of searching the disjoint path (in links or nodes) the information of the origin and destination nodes of the disjoint path to be discovered and the gateway of the path selection message that preceded the step back message.
    [2]
    2. Search for an exit door that guarantees that the sought path fulfills the condition of disjunctivity (in nodes or in links) with previous paths for the same pair of origin-destination nodes;
    [3]
    3. Complete the data structure processed according to point f) 1 with the exit port;
    [4]
    4. Update the data structure completed in a previous step of the construction of the disjoint path with the new data from point f) 3;
    [5]
    5. Process the step back message as follows:
    a) If the node has found an exit port that guarantees disjunctivity conditions according to the mode of operation, a path selection message is created and sent through the new exit port;
    b) If the node has not found an exit door that guarantees the disjunctivity conditions according to the mode of operation, the step back message is updated and forwarded to the previous node.
    characterized by
    g) In the exploration phase, step a) indicated above, the exploratory path search message generated by the originating device contains the identifier of the originating node, the type of disjoint path (disjoint in links or disjoint in nodes) to be explored, and the 1S-MDP protocol tag;
    h) In the path selection process, step b), explained above, the path selection message contains the identifiers of the source and destination nodes of the path to be discovered, the path identifier, the 1S-MDP protocol label, the type of path to discover (node disjoint or link disjoint), and the entry and exit ports next to the node to which they belong that the path selection message has traversed.
    i) In the step back process, step c), explained above, the step back message contains the identifiers of the source and destination nodes of the path to discover, the path identifier, the 1S-MDP protocol label, the type on the way to discover (disjoint in node or disjoint in link), and the entry and exit ports next to the node to which they belong that the message has passed path selection.
    j) When a device receives an exploratory message from step a), the device performs the following actions:
    1. Check if it is a destination border node If yes:
    to. It will proceed to stage b), selecting the different disjoint paths based on the information collected in stage a) by sending path selection messages with the destination address of the node that generated the exploration message, source address, its identifier, including a sequence number (or similar) that uniquely identifies the path between the pair of origin-destination nodes, and an indicator of the type of path to create (disjoint in links or in nodes), as well as the entry ports and exit and the node identifier traversing the path selection message;
    If not:
    b. Process the message as indicated in point d) 3;
    k) When a device receives a back-pass message, the node performs the following actions:
    1. Check if the destination address of the message corresponds to the node identifier.
    If so:
    a) Extract the information of the disjoint path found from the message and forward it to the device that needs it, or save said information locally, having finished the search for one of the multiple paths;
    In negative case
    b) Operate as described in steps e) 1 -e) 4;
    2. Node characterized by having the appropriate processing means to implement the method of claim 1.
    3. Switched network characterized by comprising at least one node defined according to claim 2.
    类似技术:
    公开号 | 公开日 | 专利标题
    ES2307113T3|2008-11-16|ROADING PROCEDURE IN AN AD HOC NETWORK.
    ES2339782T3|2010-05-25|HYBRID PROTOCOL OF ROADING FOR A NETWORK WITH MESH TOPOLOGY.
    US8102775B2|2012-01-24|Joining tree-based networks into an autonomous system using peer connections between the tree-based networks
    US20070086358A1|2007-04-19|Directed acyclic graph computation by orienting shortest path links and alternate path links obtained from shortest path computation
    JP2014525692A|2014-09-29|Implementation of OSPF in a split architecture network
    US20140022951A1|2014-01-23|Logical inter-cloud dispatcher
    ES2375110T3|2012-02-24|APPLIANCE AND SIGNALING ROAD PROCEDURE IN AN OPTICAL NETWORK.
    US20090296704A1|2009-12-03|Method for multi-path source routing in sensor network
    US20090161578A1|2009-06-25|Data routing method and device thereof
    US9258208B2|2016-02-09|Multiple path availability between walkable clusters
    US9413638B2|2016-08-09|Generating a loop-free routing topology based on merging buttressing arcs into routing arcs
    EP2880826A1|2015-06-10|Label distribution and route installation in a loop-free routing topology using routing arcs
    KR20130109154A|2013-10-07|Prioritization of routing information updates
    Jung et al.2014|Joint operation of routing control and group key management for 5G ad hoc D2D networks
    CN104919767A|2015-09-16|Methods and devices for implementing Shortest Path Bridging MAC mode support over a virtual private LAN service network
    ES2363083T3|2011-07-20|AUTOMATIC PROTECTION SWITCHING PROCEDURE.
    US20050254473A1|2005-11-17|Routing within a mobile communication network
    Mitton et al.2008|Hector is an energy efficient tree-based optimized routing protocol for wireless networks
    Galvez et al.2011|Multipath routing with spatial separation in wireless multi-hop networks without location information
    ES2827842B2|2022-01-28|SEARCH PROCEDURE FOR MULTIPLE DISJOINT PATHS IN A STEP AND NETWORK NODE
    ES2448791T3|2014-03-17|Method and system for automatic selection of diversion paths in a wireless mesh network
    US7701875B2|2010-04-20|OSPF unidirectional link support for unidirectional return paths
    EP3598704A1|2020-01-22|Method and apparatus for establishing domain-level topology and network system
    Islam et al.2011|An efficient routing protocol on a Dynamic Cluster-based Sensor Network
    Adeluyi et al.2012|SMiRA: A bio-inspired fault tolerant routing algorithm for MANETs
    同族专利:
    公开号 | 公开日
    ES2827842B2|2022-01-28|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    EP1773003A1|2005-10-04|2007-04-11|NTT DoCoMo, Inc.|Method and apparatus for discovering disjoint routes to multiple service nodes|
    US20090228575A1|2008-03-07|2009-09-10|Pascal Thubert|Computing disjoint paths for reactive routing mesh networks|
    US20120327792A1|2011-06-27|2012-12-27|Jianlin Guo|Method for Discovering and Maintaining Routes in Smart Meter Networks|
    WO2017158226A1|2016-03-18|2017-09-21|Universidad de Alcalá de Henares|Method for establishing and deleting multiple frame-forwarding disjoint paths, and network bridge|
    法律状态:
    2021-05-24| BA2A| Patent application published|Ref document number: 2827842 Country of ref document: ES Kind code of ref document: A1 Effective date: 20210524 |
    2022-01-28| FG2A| Definitive protection|Ref document number: 2827842 Country of ref document: ES Kind code of ref document: B2 Effective date: 20220128 |
    优先权:
    申请号 | 申请日 | 专利标题
    ES201931036A|ES2827842B2|2019-11-22|2019-11-22|SEARCH PROCEDURE FOR MULTIPLE DISJOINT PATHS IN A STEP AND NETWORK NODE|ES201931036A| ES2827842B2|2019-11-22|2019-11-22|SEARCH PROCEDURE FOR MULTIPLE DISJOINT PATHS IN A STEP AND NETWORK NODE|
    [返回顶部]